/*
445. Add Two Numbers II
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * 解法1:
 * 先链表逆序,再相加
 * 相加的结果再逆序
 */
class Solution
{
private:
    ListNode *reverseList(ListNode *l)
    {
        ListNode *pre = NULL;
        ListNode *cur = l;
        ListNode *next;
        for(; cur; cur = next) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
        }
        return pre;
    }
    ListNode *addTwoNumbers_helper(ListNode *l1, ListNode *l2)
    {
        ListNode * ret = NULL;
        ListNode **pret = &ret;
        int        val = 0;
        int        ist = 0;
        while(l1) {

            if(l2) {
                val = l1->val + l2->val + ist;
                l2 = l2->next;
            } else {
                val = l1->val + ist;
            }
            l1 = l1->next;
            *pret = new ListNode(val % 10);
            pret = &(*pret)->next;
            ist = val / 10;
        }
        while(l2) {
            val = l2->val + ist;
            l2 = l2->next;
            *pret = new ListNode(val % 10);
            pret = &(*pret)->next;
            ist = val / 10;
        }
        if(ist) {
            *pret = new ListNode(ist);
            pret = &(*pret)->next;
        }
        return ret;
    }

public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *r1 = reverseList(l1);
        ListNode *r2 = reverseList(l2);
        return reverseList(addTwoNumbers_helper(r1, r2));
    }
};

/**
 * 解法2
 * 先数出一共有多少个节点
 */